#include <stdio.h>
#include <stdlib.h>
#include  <memory.h>
/* ftruncate */
#include <unistd.h>


//#include "tree.h"
#include "file_list_tree.h"
#include "mtd_sim.h"
#include "yaffs_read.h"

static inline int
max(int a, int b) {return a > b ? a : b;}

static int
file_trunk_cmp(struct file_trunk *a, struct file_trunk *b)
{
	return a->tags.chunk_id - b->tags.chunk_id;
}

RB_HEAD(chunk_tree_t, file_trunk);
//RB_PROTOTYPE(chunk_tree_t, file_trunk, rb_entry, file_trunk_cmp);
RB_PROTOTYPE(file_list_tree_t, file_trunk_list, rb_entry, );
RB_GENERATE(chunk_tree_t, file_trunk, rb_entry, file_trunk_cmp);


static int
recover_one_version(struct mtd_info *mtd, struct file_trunk *header_chunk, int expected_min_size, int version, struct chunk_tree_t *tree)
{
	int cur_chunk_id, file_size = -1, max_valid_chunk_id = -1;
	static int no_header_version = 1;
	void *data = NULL;
	struct file_trunk *ptrunk, *ptrunk1, tmp_trunk;
	struct yaffs_obj_hdr *ptr_obj_hdr;
	struct yaffs_ext_tags tags;

	char file_name[YAFFS_MAX_NAME_LENGTH + 10];
	FILE *recovered_file = NULL;


	data = malloc(totalBytesPerChunk);

	if (!data)
		goto error;

	/* get the file name */
	if (header_chunk) {

		ptr_obj_hdr = (struct yaffs_obj_hdr *)data;
		yaffs_read_chunk_with_tags(mtd, header_chunk->trunk_number, data, &tags);
		sprintf(file_name, "%s_v%d", ptr_obj_hdr->name, version);

		file_size = ptr_obj_hdr->file_size;
		
		/* the file is shrinked, 
		 * but the hdr indicating the original file content is lost.*/
		if (file_size < expected_min_size)
			/*TODO: finer recovery?*/;

		/* here we assume the issue above has been handled and
		 * we can discard the truncated file contents */
		max_valid_chunk_id = (file_size / chunkSize) + 1;
		tmp_trunk.tags.chunk_id = max_valid_chunk_id;
		ptrunk = RB_NFIND(chunk_tree_t, tree, &tmp_trunk);
		ptrunk = ptrunk != NULL ? RB_NEXT(chunk_tree_t, tree, ptrunk) : NULL;
		while (ptrunk) {
			ptrunk1 = RB_NEXT(chunk_tree_t, tree, ptrunk);
			RB_REMOVE(chunk_tree_t, tree, ptrunk);
			ptrunk = ptrunk1;
		}

	} else {

		sprintf(file_name, "noheader_v%d", no_header_version++);
	}

	/* start recovery */	

	recovered_file = fopen(file_name, "w+");

	if (!recovered_file)
		goto error;
	
	RB_FOREACH(ptrunk, chunk_tree_t, tree) {
		cur_chunk_id = ptrunk->tags.chunk_id;
		
		fseek(recovered_file, (cur_chunk_id - 1) * chunkSize, SEEK_SET);
		yaffs_read_chunk_with_tags(mtd, ptrunk->trunk_number, data, &tags);
		fwrite(data, tags.n_bytes, 1, recovered_file);
	}
	
	/* There may be a hole at the end of the file 
	 * XXX: POSIX only */
	if (file_size != -1)
		ftruncate(fileno(recovered_file), file_size);



	fclose(recovered_file);
	free(data);

	return 0;

error:
	if (data)
		free(data);

	if (recovered_file)
		fclose(recovered_file);
	return -1;
}

static int
recover_by_trunk_list(struct mtd_info *mtd, struct file_trunk_list *ptr_trunk_list)
{
	/* assert chunk_list is a file's */
	int cur_size, version, num_headers_found;

	struct list_head *chunk_list = &ptr_trunk_list->chunk_list;
	struct list_head *ptr_iter, *ptr_last_hdr; 
	struct file_trunk *ptr_list_ele, *ptr_tmp_trunk;

	struct chunk_tree_t chunk_tree;

	/* XXX: we have not considered directories yet! */
	if (ptr_trunk_list->obj_type != YAFFS_OBJECT_TYPE_FILE)
		return 0;

	version = 1;
	num_headers_found = 0;
	cur_size = 0;
	
	RB_INIT(&chunk_tree);
	list_for_each(ptr_iter, chunk_list) {

		ptr_list_ele = list_entry(ptr_iter, struct file_trunk, list_entry);
		if (ptr_list_ele->tags.chunk_id == 0) {

			ptr_last_hdr = ptr_iter;
			ptr_list_ele->num_headers_before = num_headers_found++;
			recover_one_version(mtd, ptr_list_ele, cur_size, version++, &chunk_tree);
			cur_size = 0;

		} else { /* if (ptr_list_ele->tags.chunk_id == 0) */
			cur_size = max(cur_size, (ptr_list_ele->tags.chunk_id - 1) * chunkSize + ptr_list_ele->tags.n_bytes);

			ptr_list_ele->num_headers_before = num_headers_found;

			/* find if there is already one */
			ptr_tmp_trunk = RB_FIND(chunk_tree_t, &chunk_tree, ptr_list_ele);

			/* remove the older chunk */
			if (ptr_tmp_trunk) {
				/* a header may be lost between ptr_tmp_trunk and ptr_list_ele */
				if (ptr_tmp_trunk->num_headers_before == num_headers_found)
					/*TODO: finer recover?*/;

				RB_REMOVE(chunk_tree_t, &chunk_tree, ptr_tmp_trunk);
			}

			RB_INSERT(chunk_tree_t, &chunk_tree, ptr_list_ele);
						
		} 

	} /* list_foreach */

	/* if the last chunk is not a obj hdr,
	 * we should do one more recovery */
	if (ptr_last_hdr != chunk_list->prev) {
		ptr_list_ele = list_entry(ptr_last_hdr, struct file_trunk, list_entry);
		recover_one_version(mtd, ptr_list_ele, cur_size, version++, &chunk_tree);
	}

	return 0;

}

int
file_recover_iterate_tree(struct mtd_info *mtd, struct file_list_tree_t *ptree)
{
	file_list_tree_iterate(mtd, ptree, recover_by_trunk_list);
//	struct file_trunk_list *ptr_tree_ele;
	//struct file_trunk *ptrunk_ele, *ptrunk_ele1;
	
//	RB_FOREACH(ptr_tree_ele, file_list_tree_t, ptree){
//		recover_by_trunk_list(mtd, &ptr_tree_ele->chunk_list);
//	}
	return 0;

}

